package com.leetcode.algorithm.y22.m08.w1;

/**
 * 547. 省份数量
 * 
 * https://leetcode.cn/problems/number-of-provinces/
 * 
 * @author jie.deng
 *
 */
class Question0547Solution01 {
	
	public int findCircleNum(int[][] isConnected) {
		int n = isConnected.length;
		UnionFind uf = new UnionFind(n);
		for (int i = 0; i < isConnected.length; i++) {
			for (int j = 0; j < isConnected.length; j++) {
				if (isConnected[i][j] == 1) {
					uf.union(i, j);
				}
			}
		}
		return uf.count;
	}

	class UnionFind {
		// 实际存储的是parent
		int roots[];
		int count;

		public UnionFind(int size) {
			roots = new int[size];
			for (int i = 0; i < size; i++) {
				roots[i] = i;
			}
			count = size;
		}

		private int findRoot(int x) {
			if (x == roots[x]) {
				return x;
			}
			// 路径压缩
			return x = findRoot(roots[x]);
		}

		public void union(int x, int y) {
			int rootX = findRoot(x);
			int rootY = findRoot(y);
			if (rootX != rootY) {
				roots[rootY] = rootX;
				count--;
			}
		};

	}    
}